//
//  BTree.m
//  SimulacraDB
//
//  Created by Andre Cohen on 8/11/08.
//  Copyright 2008 __MyCompanyName__. All rights reserved.
//

#import "BTree.h"


@implementation BTree

static int order = 4;

- (id)init {
	[super init];
	root = [BTreeNode createBTreeNode];
	return self;
}

- (void)load:(NSString *)name {
	if([[NSFileManager defaultManager] fileExistsAtPath:[NSString stringWithFormat:@"%@.btree",name]])
		root = [NSKeyedUnarchiver unarchiveObjectWithFile:[NSString stringWithFormat:@"%@.btree",name]];
}

- (void)save:(NSString *)name {
	[NSKeyedArchiver archiveRootObject:root toFile:[NSString stringWithFormat:@"%@.btree",name]];
}

- (void)insertObject:(IndexRecord *)object {
	NSArray *path = [self findLeafFor:object];
	int level = [path count]-1;
	bool added = false;
	int middle;
	
	BTreeNode *current;
	BTreeNode *newChild = nil;
	
	for(;level>=0;level--){
		current = [path objectAtIndex:level];
		
		if([current isLeaf]){
			if([[current keys] count] + 1 < order){
				[self insertInOrder:object edge:nil into:current];
				added = true;
			}else{
				[self insertInOrder:object edge:nil into:current];
				newChild = [BTreeNode createBTreeNode];
				middle = [[current keys] count]/2;
				while(middle<[[current keys] count]){
					[[newChild keys] addObject:[[current keys] objectAtIndex:middle]];
					[[current keys] removeObjectAtIndex:middle];
				}
				[current setSibling:newChild];
			}
		}else if(newChild!=nil){
			if(current !=nil && [[current keys] count]<order){
				[self insertInOrder:[[newChild keys] objectAtIndex:0] edge:newChild into:current];
				if(![newChild isLeaf])
					[[newChild keys] removeObjectAtIndex:0];
				newChild = nil;
			}else{
				[self insertInOrder:[[newChild keys] objectAtIndex:0] edge:newChild into:current];
				if(![newChild isLeaf])
					[[newChild keys] removeObjectAtIndex:0];
				
				newChild = [BTreeNode createBTreeNode];
				middle = [[current keys] count]/2;
				while(middle<[[current keys] count]){
					[[newChild keys] insertObject:[[current keys] objectAtIndex:[[current keys] count]-1] atIndex:0];
					[[newChild edges] insertObject:[[current edges] objectAtIndex:[[current edges] count]-1] atIndex:0];
					[[current keys] removeObjectAtIndex:[[current keys] count]-1];
					[[current edges] removeObjectAtIndex:[[current edges] count]-1];
				}
				//[[newChild edges] addObject:[[current edges] objectAtIndex:middle]];

				if(current == root){
					root = [BTreeNode createBTreeNode];
					[[root keys] addObject:[[newChild keys] objectAtIndex:0]];
					[[newChild keys] removeObjectAtIndex:0];
					
					[[root edges] addObject:current];
					[[root edges] addObject:newChild];
					newChild = nil;
				}
			}
		}
	}
	if(newChild!=nil){
		root = [BTreeNode createBTreeNode];
		[[root keys] addObject:[[newChild keys] objectAtIndex:0]];
		[[root edges] addObject:current];
		[[root edges] addObject:newChild];
	}
}

- (void)removeObject:(IndexRecord *)object {
	NSArray *path = [self findLeafFor:object];
	int level = [path count]-1;
	int i; 
	
	BTreeNode *current = nil, *sibling = nil, *parent = nil;
	IndexRecord *oldChild = nil,*newSmaller = nil;
	for(;level>=0;level--){
		current = [path objectAtIndex:level];
		if(level-1>=0)
			parent = [path objectAtIndex:level-1];
		else 
			parent = nil;
		
		if([current isLeaf]){
			if(current == root){
				[self removeKey:object from:current];
				return;
			}else if([[current keys] count]-1>order/2){
				[self removeKey:object from:current];
				oldChild = nil;
				newSmaller = [[current keys] objectAtIndex:0];
			}else{
				char direction = 'r';
				IndexRecord *oldKey, *newKey;
				
				sibling = [self siblingOf:current parent:[path objectAtIndex:level-1] direction:1];
				if(sibling==nil){
					direction = 'l';
					sibling = [self siblingOf:current parent:[path objectAtIndex:level-1] direction:-1];
				}
				
				[self removeKey:object from:current];
				
				if([[sibling keys] count]-1>order/2){
					if(direction=='r'){
						oldKey = [[sibling keys] objectAtIndex:0];
						[self insertInOrder:[[sibling keys] objectAtIndex:0] edge:nil into:current];
						[[sibling keys] removeObjectAtIndex:0];
						newKey = [[sibling keys] objectAtIndex:0];
						newSmaller = [[current keys] objectAtIndex:0];
					}else{
						if([[current keys] count] && [self isRecord:[[current keys] objectAtIndex:0] lessThan:object])
							oldKey = [[current keys] objectAtIndex:0];
						else 
							oldKey = object;
						[self insertInOrder:[[sibling keys] objectAtIndex:[[sibling keys] count]-1] edge:nil into:current];
						[[sibling keys] removeObjectAtIndex:[[sibling keys] count]-1];
						newKey = [[current keys] objectAtIndex:0];
					}
					[self replaceKey:oldKey with:newKey inNode:parent];
					if(newSmaller == nil)
						return;
				}else{
					if(direction=='r'){
						oldChild = [[sibling keys] objectAtIndex:0];
						for(i=0;i<[[sibling keys] count];i++)
							[self insertInOrder:[[sibling keys] objectAtIndex:i]
										   edge:nil 
										   into:current];
						newSmaller = [[current keys] objectAtIndex:0];
						//[self replaceKey:oldChild with:[[current keys] objectAtIndex:0] inNode:[path objectAtIndex:level-1]];
					}
					else{
						if([[current keys] count] && [self isRecord:[[current keys] objectAtIndex:0] lessThan:object])
							oldChild = [[current keys] objectAtIndex:0];
						else 
							oldChild = object;
						for(i=0;i<[[current keys] count];i++)
							[self insertInOrder:[[current keys] objectAtIndex:i]
										   edge:nil 
										   into:sibling];
						//newSmaller = [[sibling keys] objectAtIndex:0];
						//[self replaceKey:object with:[[sibling keys] objectAtIndex:0] inNode:[path objectAtIndex:level-1]];
					}
					
				}
			}
		}else if(oldChild!=nil){
			for(i=0;i<[[current keys] count];i++){
				if(oldChild!=nil && [self isRecord:[[current keys] objectAtIndex:i] equalTo:oldChild]){
					[[current keys] removeObjectAtIndex:i];
					[[current edges] removeObjectAtIndex:i+1];
					oldChild = nil;
				}
				else if([self isRecord:[[current keys] objectAtIndex:i] equalTo:object]){
					[[current keys] removeObjectAtIndex:i];
					[[current keys] insertObject:[self smallestOf:[[current edges] objectAtIndex:i+1]] atIndex:i];
				}
			}
			
			if(oldChild!=nil || [[current edges] count]<2){
				if(current==root){
					root = [[current edges] objectAtIndex:0];
					if([root isLeaf])
						[[root edges] removeAllObjects];
					else
						[[current edges] removeObjectAtIndex:0];
					return;
				}	
				
				char direction = 'r';
				sibling = [self siblingOf:current parent:[path objectAtIndex:level-1] direction:1];
				if(sibling == nil){
					direction = 'l';
					sibling = [self siblingOf:current parent:[path objectAtIndex:level-1] direction:-1];
				}
				
				
				int sSize = [[sibling keys] count]-(order/2);
				int mSize = order/2;
				if(sSize>mSize){
					// Find pivot in parent
					int pivot = -1;
					if(direction=='r'){
						// Find pivot between current & sibling
						for(i=0;i<[[parent edges] count] && pivot<0;i++)
							if([[parent edges] objectAtIndex:i]==sibling)
								pivot = i-1;
							   
						while([[current keys] count]<order/2){
							// Parent key to current
							[[current keys] addObject:[[parent keys] objectAtIndex:pivot]];
							// Parent key edge from sibling to current
							[[current edges] addObject:[[sibling edges] objectAtIndex:0]];
							// Remove parent key
							[[parent keys] removeObjectAtIndex:pivot];
							// Add new key from sibling
							[[parent keys] addObject:[[sibling keys] objectAtIndex:0]];
							// Remove key and edge
							[[sibling keys] removeObjectAtIndex:0];
							[[sibling edges] removeObjectAtIndex:0];
						}
					}else{
						// Find pivot between current & sibling
						for(i=0;i<[[parent edges] count] && pivot<0;i++)
							if([[parent edges] objectAtIndex:i]==sibling)
								pivot = i;
						
						while([[current keys] count]<order/2){
							// Parent key to current
							[[current keys] insertObject:[[parent keys] objectAtIndex:pivot] atIndex:0];
							// Parent key edge from sibling to current
							[[current edges] addObject:[[sibling edges] objectAtIndex:[[sibling edges] count]-1]];
							// Remove parent key
							[[parent keys] removeObjectAtIndex:pivot];
							// Add new key from sibling
							[[parent keys] addObject:[[sibling keys] objectAtIndex:[[sibling keys] count]-1]];
							// Remove key and edge
							[[sibling keys] removeObjectAtIndex:[[sibling keys] count]-1];
							[[sibling edges] removeObjectAtIndex:[[sibling edges] count]-1];
						}
					}
				}else{
					oldChild = nil;
					if(direction=='r'){
						for(i=0;i<[[parent edges] count] && oldChild==nil;i++)
							if([[parent edges] objectAtIndex:i]==sibling)
								oldChild = [[parent keys] objectAtIndex:i-1];
						
						[self insertInOrder:oldChild edge:nil into:current];
						
						for(i=0;i<[[sibling keys] count];i++){
							[[current keys] addObject:[[sibling keys] objectAtIndex:i]];
							[[current edges] addObject:[[sibling edges] objectAtIndex:i]];
						}
						[[current edges] addObject:[[sibling edges] objectAtIndex:i]];
					}else{
						for(i=0;i<[[parent edges] count] && oldChild==nil;i++)
							if([[parent edges] objectAtIndex:i]==current)
								oldChild = [[parent keys] objectAtIndex:i-1];
					
						[self insertInOrder:[self smallestOf:[[current edges] objectAtIndex:0]] edge:nil into:sibling];
						
						for(i=0;i<[[current keys] count];i++){
							[[sibling keys] addObject:[[current keys] objectAtIndex:i]];
							[[sibling edges] addObject:[[current edges] objectAtIndex:i]];
						}
						[[sibling edges] addObject:[[current edges] objectAtIndex:i]];
					}
				}
			}
		}else if(newSmaller!=nil){
			for(i=0;i<[[current keys] count] && newSmaller!=nil;i++)
				if([[[current keys] objectAtIndex:i] equalTo:object]){
					[[current keys] removeObjectAtIndex:i];
					[[current keys] insertObject:newSmaller atIndex:i];
					newSmaller = nil;
				}
		}
	}
}

- (IndexRecord *)smallestOf:(BTreeNode *)node {
	BTreeNode *current = node;
	while(true){
		if([current isLeaf]){
			return [[current keys] objectAtIndex:0];
		}
		current = [[current edges] objectAtIndex:0];
	}
}

- (void)replaceKey:(IndexRecord *)oldKey with:(IndexRecord *)newKey inNode:(BTreeNode *)node {
	int i;
	for(i=0;i<[[node keys] count];i++)
		if([self isRecord:[[node keys] objectAtIndex:i] equalTo:oldKey]){
			[[node keys] removeObjectAtIndex:i];
			[[node keys] insertObject:newKey atIndex:i];
			return;
		}
}

- (void)removeKey:(IndexRecord *)object from:(BTreeNode *)node {
	int i;
	for(i=0;i<[[node keys] count];i++)
		if([self isRecord:[[node keys] objectAtIndex:i] equalTo:object]){
			[[node keys] removeObjectAtIndex:i];
			return;
		}
}
											
- (NSArray *)findLeafFor:(IndexRecord *)object {
	NSMutableArray *stack = [[[NSMutableArray alloc] init] autorelease];
	BTreeNode *curr = root;
	
	if(curr==nil)
		return nil;
	
	while(true){
		bool found = FALSE;
		int i = 0;
		
		[stack addObject:curr];
		
		if([[curr edges] count]>1){
			// Node
			for(i=0;i<[[curr keys] count] && !found;i++) {
				if([self isRecord:object lessThan:[[curr keys] objectAtIndex:i]]){
					curr = [[curr edges] objectAtIndex:i];
					found = true;
				}
			}
			if(found==FALSE)
				curr = [[curr edges] objectAtIndex:[[curr edges] count]-1];
		}else{
			// Lead
			return stack;
		}
	}
	return nil;	
}

- (IndexRecord *)findObject:(IndexRecord *)object {
	NSArray *stack = [self findLeafFor:object];
	BTreeNode *found = [stack objectAtIndex:[stack count]-1];
	
	if(found!=nil){
		int i;
		for(i=0;i<[[found keys] count];i++)
			if([self isRecord:object equalTo:[[found keys] objectAtIndex:i]])
				return [[found keys] objectAtIndex:i];
		return nil;
	}
	return nil;
}

- (BTreeNode *)insertInOrder:(IndexRecord *)object edge:(BTreeNode *)edge into:(BTreeNode *)node {
	int i;
	for(i=0;i<[[node keys] count];i++)
		if([self isRecord:object lessThan:[[node keys] objectAtIndex:i]]){
			[[node keys] insertObject:object atIndex:i];
			if(edge!=nil){
				[[node edges] insertObject:edge atIndex:i+1];
			}
			return node;
		}
	[[node keys] addObject:object];
	if(edge!=nil)
		[[node edges] addObject:edge];
	return node;
}

- (BTreeNode *)siblingOf:(BTreeNode *)node parent:(BTreeNode *)parent direction:(int)d {
	if(parent==nil)
		return nil;
	int i;
	for(i=0;i<[[parent edges] count];i++)
		if(node == [[parent edges] objectAtIndex:i])
			if(i+d>=0 && i+d<[[parent edges] count])
				return [[parent edges] objectAtIndex:i+d];
	return nil;
}

-(BOOL)isRecord:(IndexRecord *)a lessThan:(IndexRecord *)b {
	return [a lessThan:b];
}
-(BOOL)isRecord:(IndexRecord *)a greaterThan:(IndexRecord *)b {
	return [a greaterThan:b];
}
-(BOOL)isRecord:(IndexRecord *)a equalTo:(IndexRecord *)b {
	return [a equalTo:b];
}

- (void)inOrder:(BTreeNode *)current {
	if(current == nil)
		current = root;
	int i;
	if([[current edges] count]<2){
		for(i=0;i<[[current keys] count];i++)
			printf("%s ",[[[[current keys] objectAtIndex:i] description] UTF8String]);
		printf("\n");
	}else{
		if([[current edges] count]!=[[current keys] count]+1)
			printf("******");
		printf("%d: ",[[current edges] count]);
		for(i=0;i<[[current keys] count];i++)
			printf("(%s)",[[[[[current keys] objectAtIndex:i] rid] description] UTF8String]);
		printf("\n");
		for(i=0;i<[[current edges] count];i++)
			[self inOrder:[[current edges] objectAtIndex:i]];
	}
}

@end
